The present invention relates generally to computer graphics. In particular, the present Invention relates to dynamically triangle stripping a multi-resolution mesh (xe2x80x9cMRMxe2x80x9d) representation of a three-dimensional (xe2x80x9c3-Dxe2x80x9d) triangulated model.
Prior art approaches to increase the speed of rendering and displaying three dimensional objects have started with the properties of the polygons used to render an object. A common polygon used in rendering three dimensional objects is a triangle. A triangle has many helpful properties that make it ideal for use in rendering three dimensional surfaces. For example, a triangle is completely defined by three vertices and each triangle also uniquely defines a plane. Thus, many systems will use a plurality of triangles to render a three dimensional surface. If each triangle is passed separately to the graphic subsystem that renders the three dimensional object, then three vertices for each triangle must be passed and processed by the graphic subsystem. However, the number of vertices that must be passed and processed by the graphic subsystem can be reduced through xe2x80x9cvertex sharing.xe2x80x9d Vertex sharing relies on a property of shared sides among triangles. Although it takes three vertices to define one triangle, it only takes four vertices to define two triangles if they share a common side. In order to take advantage of vertex sharing to reduce the number of vertices needed to render an object, pipelined systems have been developed that divide a three dimensional object into triangle strips that can then be processed and displayed efficiently In order to present a three-dimensional (xe2x80x9c3-Dxe2x80x9d) object on a display screen, typical computer graphics systems decompose the object into a plurality of graphics primitives. These primitives are the basic components of a graphics picture and may include points, lines, polylines, vectors and polygons, such as triangles or quadrilaterals. Typically, a hardware/software scheme is implemented to render, or draw, on the two-dimensional display screen, the graphics primitives that represent the view of one or more objects being represented on the screen.
In general, the primitives that define a 3-D graphic object are provided from a host computer, which defines each primitive in terms of primitive data. For example, when the primitive is a triangle, the host computer may define the primitive in terms of the x, y, z coordinates of its vertices, as well as the R, G, B color values of each vertex. Rendering hardware interpolates the primitive data to compute the display screen pixels that are turned on to represent each primitive, and the R, G, B values for each pixel.
A triangle strip (tri-strip) is a basic primitive that very efficiently represents the triangles (faces) of a mesh. A xe2x80x9cmesh,xe2x80x9d as used in the present invention, is a representation of the surface area of an object by subdividing the surface area into triangle or quadrilateral shapes. For example, if there are ten triangles in a row, it would take thirty vertices (3 vertices per triangle*ten triangles) to represent these triangles as discrete elements within the 3-D object.
Triangle strips have been typically pre-computed for each mesh because current triangle stripping processes are too slow to be computed each time the mesh is rendered. As a result, this pre-computing technique does not work with Multi-Resolution Meshes (xe2x80x9cMRMsxe2x80x9d) because the triangle strips have to be computed and stored for every possible resolution of the MRM, thus using far too much memory.
In a triangle mesh a xe2x80x9cneighboring trianglexe2x80x9d is any triangle that shares an edge with an adjacent triangle. Similarly, a xe2x80x9cfar cornerxe2x80x9d of a triangle is the corner in the neighboring triangle that is not on the edge that joins a triangle to its neighboring triangles. A xe2x80x9cfar vertexxe2x80x9d is the vertex that defines the far corner.
Previous triangle mesh data structures were variable in size or limited to manifold meshes. In a xe2x80x9cmanifoldxe2x80x9d mesh each shared edge can only be shared between two triangles. These previous triangle mesh data structures also comprised triangle records that included individual pointers to the neighboring triangles and location information for each of the three corners/vertices of the triangle. As a consequence of these structures, all of the vertices in the triangle must be searched to find the far vertex, the size of the data structures is variable and usually larger which results in slower performance, and variable-sized sets of pointers were used to store the pointers to multiple neighbors in non-manifold meshes that shared an edge. In a xe2x80x9cnon-manifold meshxe2x80x9d at least one edge is shared by more than two triangles. While variable-sized sets of pointers are relatively easy to implement in software, they do not easily lend themselves to being implemented in hardware.
FIG. 7 illustrates an exemplary prior art triangle mesh data structure. In FIG. 7, an exemplary three triangle mesh 700 which is made up of triangles T1, T2 and T3701, 702 and 703, respectively, is shown with the comers of each triangle labeled as C0, C1 and C2. A triangle mesh data structure 705 illustrates the interrelationships between triangle records 710, 720 and 730 which represent triangles T1701, T2702 and T3703, respectively, of triangle mesh 700. Triangle record T1710 is comprised of a triangle number field 711, a corner 0 field 712, a corner 1 field 713, a corner 2 field 714, a record header 715, a first neighboring triangle pointer 716, a second neighboring triangle pointer 717 and a third neighboring triangle pointer 718. Each of the pointers 716, 717 and 718 are used to point to the header record of a different neighboring triangle. For example, in FIG. 7, since triangle T1701 and triangle T2702 are neighbors, first neighboring triangle pointer 716 of triangle record T1710 points to the record header 725 for triangle record T2720. Similarly, first neighboring triangle pointer 726 of triangle record T2720 points to the record header 715 for triangle record T1710. Continuing, second neighboring triangle pointer 727 of triangle record T2720 points to the record header 735 for triangle record T3730 and first neighboring triangle pointer 736 of triangle record T3730 points to the record header 725 for triangle record T2720, since triangle T2702 and triangle T3703 are neighbors. The second and third neighboring triangle pointers 717 and 718, respectively, in triangle record T1710 are null pointers since only one side of triangle T1701 has a neighbor triangle, triangle B 702.
Selective refinement of an arbitrary progressive mesh according to changing view parameters is introduced by Hughes Hoppe in xe2x80x9cView-Dependent Refinement of Progressive Meshes,xe2x80x9d SIGGRAPH 97.
A general representation of a pipeline system processing a triangle strip is described in U.S. Pat. No. 5,818,136 to Keondjian. This discussion highlights two hallmarks of prior art pipelined systems. First, the pipelined process always works on one vertex at a time, and for each vertex processed, after the first two vertices, a new triangle is drawn. Second, to maintain maximum performance, the pipeline must be provided with a steady stream of vertices and any breaks in the steady flow of vertices reduces system performance.
Therefore, it can be appreciated that a substantial need exists to provide an improved method and system for dynamic triangle stripping a MRM at run-time at rates at least as fast as standard computer display rates of 60 Hz.
Embodiments of the present invention provide a method for creating a neighbor mesh from a multi-resolution mesh. The method includes computing neighbor data for the neighbor mesh at a highest resolution of the multi-resolution mesh. The method further includes changing the resolution of the multi-resolution mesh and re-computing the neighbor data for the neighbor mesh at the changed resolution of the multi-resolution mesh, and computing an updated neighbor mesh from the re-computed neighbor data.